package 我的Java学习_算法基础.day_07;

/**
 * @author 挚爱之夕
 * @date 2021/8/19 - 08 - 19 - 15:57
 * @Description: 我的暑假Java学习.day_06
 * @Version: 1.0
 */
public class _107_硬币表示某个给定数值 {
    public static void main(String[] args) {
        for(int i = 1;i<=30;i++){
            int n = countWay(i);
            System.out.println(i+"-----"+n);
        }
    }
    private static int countWay(int n){
        if(n<=0) return 0;
        return countWay(n,new int[]{1,5,10,25},3);
    }

    /**
     *
     * @param n 总钱数
     * @param coins 可供选择的面值数组
     * @param index 可选最大面值对应的数组下标
     * @return 总的组合数
     */
    private static int countWay(int n,int[] coins,int index){
        if(index==0){
            return 1;
        }
        int res = 0;
        //不要最大面值
        //要1个
        //要两个
        //、、、、、、到能要最多
        for(int i =0;i*coins[index]<=n;i++){ //先考虑最大面值，剩余递归调用自身
            int residue =  n -i*coins[index];
            res+=countWay(residue,coins,index-1);
        }
        return res;
    }

}
